'''ex1'''

class Graph:
    def __init__(self):
        self.nodes = {}  # 字典，键为节点值，值为与该节点相连的节点及其权重
        self.edges = []  # 列表，存储边的信息（起点，终点，权重）

    def add_new_node(self, value, connections=None, weights=None):
        """
        添加一个新节点，并将其连接到指定的节点上，同时可以设置连接的权重。
        
        :param value: 新节点的值
        :param connections: 与新节点相连的节点列表
        :param weights: 与connections中节点相连的权重列表，与connections一一对应
        """
        if connections is None:
            connections = []
        if weights is None:
            weights = [1] * len(connections)  # 默认权重为1

        if len(connections) != len(weights):
            raise ValueError("Connections and weights must have the same length.")

        self.nodes[value] = {}
        for node, weight in zip(connections, weights):
            self.nodes[value][node] = weight
            self.edges.append((value, node, weight))
            if node not in self.nodes:
                self.nodes[node] = {}
            if node in self.nodes and value not in self.nodes[node]:
                self.nodes[node][value] = weight

    def print_my_graph(self):
        """
        打印图的表示形式。
        """
        for node, connections in self.nodes.items():
            print(f"{node}: {connections}")

    def print_edges(self):
        """
        返回并打印所有的边及其权重。
        """
        for edge in self.edges:
            print(f"({edge[0]}, {edge[1]}), weight: {edge[2]}")

# 示例用法
graph = Graph()
graph.add_new_node("A", ["B", "C"], [2, 3])
graph.add_new_node("B", ["A", "D"], [2, 1])
graph.add_new_node("C", ["A"], [3])
graph.add_new_node("D", ["B"], [1])

graph.print_my_graph()
print("\nEdges:")
graph.print_edges()

'''ex2'''

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        current = queue.popleft()
        print(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}
bfs(graph, 'A')

'''ex3'''

from collections import deque

def dfs(graph, start, visited=set()):
    if start not in visited:
        print(start)
        visited.add(start)
        for neighbor in graph[start]:
            dfs(graph, neighbor, visited)
            
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
    }
dfs(graph, 'A')

'''ex4'''

class Graph:
    def __init__(self):
        self.nodes = {}  # 字典，键为节点值，值为与该节点相连的节点列表
        self.edges = []  # 列表，存储边的信息（起点，终点）

    def add_new_node(self, value, connections=None):
        """
        添加一个新节点，并将其连接到指定的节点上。

        :param value: 新节点的值
        :param connections: 与新节点相连的节点列表
        """
        if connections is None:
            connections = []

        self.nodes[value] = connections
        for node in connections:
            if node not in self.nodes:
                self.nodes[node] = []
            if value not in self.nodes[node]:
                self.nodes[node].append(value)
            self.edges.append((value, node))

    def nodes_iter(self):
        """
        返回一个包含所有节点的迭代器。
        """
        return iter(self.nodes.keys())

    def print_my_graph(self):
        """
        打印图的表示形式。
        """
        for node, connections in self.nodes.items():
            print(f"{node}: {connections}")

    def print_edges(self):
        """
        返回并打印所有的边。
        """
        for edge in self.edges:
            print(f"({edge[0]}, {edge[1]})")

def welsh_powell_coloring(graph):
    colors = {node: None for node in graph.nodes_iter()}  # 使用新的方法来迭代节点
    vertices = list(graph.nodes_iter())
    vertices.sort(key=lambda x: len(graph.nodes[x]))
    for vertex in vertices:
        used_colors = {colors[neighbor] for neighbor in graph.nodes[vertex] if colors[neighbor] is not None}
        color = 1
        while color in used_colors:
            color += 1
        colors[vertex] = color
    return colors

graph = Graph()
graph.add_new_node("A", ["B", "C"])
graph.add_new_node("B", ["A", "D"])
graph.add_new_node("C", ["A"])
graph.add_new_node("D", ["B"])

graph.print_my_graph()
print("\nEdges:")
graph.print_edges()

colors = welsh_powell_coloring(graph)
for vertex, color in colors.items():
    print(f"Vertex {vertex} has color {color}")
'''ex5'''

import networkx as nx
import matplotlib.pyplot as plt

def draw_graph(graph):
    G = nx.Graph()
    edges = [(u, v) for u, neighbors in graph.items() for v in neighbors]
    G.add_edges_from(edges)
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True)
    plt.show()

